package 极客算法训练营.chapter06;

import java.util.*;

public class N叉树的前序遍历 {

    class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    class Solution {
        public List<Integer> preorder(Node root) {
            List<Integer> res = new ArrayList<>();
            recursionTree(root, res);
            return res;
        }

        public void recursionTree(Node node, List<Integer> res) {
            if (node == null) return;
            res.add(node.val);
            for (Node child : node.children) {
                recursionTree(child, res);
            }
        }
    }

    class Solution2 {
        public List<Integer> preorder(Node root) {
            List<Integer> res = new ArrayList<>();
            Deque<Node> stack = new LinkedList<>();
            if (root == null) return res;
            stack.push(root);
            while (!stack.isEmpty()) {
                //先添加父节点
                Node pop = stack.pop();
                res.add(pop.val);
                List<Node> children = pop.children;
                //把子节点逆序后入栈，保证子节点的弹出顺序为从左到右
                Collections.reverse(children);
                for (Node child : children) {
                    stack.push(child);
                }
            }
            return res;
        }
    }
}
